// Created by WXX on 2022/1/7 13:19
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：24 ms, 在所有 C++ 提交中击败了73.02%的用户
 * 内存消耗：11.7 MB, 在所有 C++ 提交中击败了57.93%的用户
 */
// 必胜态：可以到达某个必败态；必败态：只能到达必胜态
class Solution {
public:
    unordered_map<string, bool> hash;

    bool canWin(string s) {
        if (hash.count(s)) return hash[s];
        for (int i = 0; i + 1 < s.size(); i++)
            if (s[i] == '+' && s[i + 1] == '+') {
                if (!canWin(s.substr(0, i) + "--" + s.substr(i + 2)))
                    return hash[s] = true;
            }
        return hash[s] = false;
    }
};

int main() {

    cout << Solution().canWin("++++") << endl;  // true

    return 0;
}
